BZOJ 3996 线性代数

Description

给出一个NN的矩阵B和一个1N的矩阵C。求出一个1N的01矩阵A.使得
D=(A\
B-C)*A^T最大。其中A^T为A的转置。输出D

Input

第一行输入一个整数N,接下来N行输入B矩阵,第i行第J个数字代表Bij.
接下来一行输入N个整数,代表矩阵C。矩阵B和矩阵C中每个数字都是不超过1000的非负整数。

Output

输出最大的D

Sample Input

3
1 2 1
3 1 0
1 2 3
2 3 7

Sample Output

2

Hint

1<=N<=500

Solution

不小心看到网络流标签……
然后就非常水了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>

#define maxd 500+5
#define maxn 260000+5
#define maxm 1600000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

struct sides{
int u,v,c;
int next;
}s[maxm];

queue<int> q;
int h[maxn];
int a[maxd][maxd],c[maxd];
int first[maxn],cur[maxn],ind;
int n,S,T,ans;

int hash(int x,int y)
{

return x*n+y;
}

void insert(int u,int v,int c)
{

s[ind]=(sides){u,v,c,first[u]},first[u]=ind++;
s[ind]=(sides){v,u,0,first[v]},first[v]=ind++;
}

bool bfs()
{

set(h,-1),h[T]=0;
q.push(T);
while( !q.empty() ){
int sd=q.front();q.pop();
for(int i=first[sd];i!=-1;i=s[i].next)
if( s[i^1].c>0 && h[s[i].v]==-1 ){
h[s[i].v]=h[sd]+1;
q.push(s[i].v);
}
}
return h[S]!=-1;
}

int dfs(int x,int flow)
{

if( x==T ) return flow;
int used=0;
for(int &i=cur[x];i!=-1;i=s[i].next)
if( h[s[i].v]+1==h[x] && s[i].c>0 ){
int w=dfs(s[i].v,min(s[i].c,flow-used));
s[i].c-=w,s[i^1].c+=w,used+=w;
if( used==flow ) return flow;
}
return used;
}

void dinic()
{

while( bfs() ){
for(int i=S;i<=T;i++)
cur[i]=first[i];
ans-=dfs(S,INT_MAX);
}
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("3996.in","r",stdin);
freopen("3996.out","w",stdout);
#endif
scanf("%d",&n);
set(first,-1);
S=0,T=n*n+n+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
ans+=a[i][j];
}
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
int sup=hash(i,j);
insert(S,sup,a[i][j]);
insert(sup,i,a[i][j]);
insert(sup,j,a[i][j]);
}
for(int i=1;i<=n;i++)
insert(i,T,c[i]);
dinic();
printf("%d",ans);
return 0;
}